{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chapter_decrease_and_conquer.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/liyin2015/Algorithms-and-Coding-Interviews/blob/master/chapter_decrease_and_conquer.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hIhy6_m3lvTV",
        "colab_type": "text"
      },
      "source": [
        "## Binary Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HoaV8uZHl1G-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "nums = [1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Q9iK9qbomHqz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title Standard binary search\n",
        "def standard_binary_search(lst, target):\n",
        "    l, r = 0, len(lst) - 1\n",
        "    while l <= r:\n",
        "        mid = l + (r - l) // 2\n",
        "        if lst[mid] == target:\n",
        "            return mid\n",
        "        elif lst[mid] < target:\n",
        "            l = mid + 1\n",
        "        else:\n",
        "            r = mid - 1\n",
        "    return -1 # target is not found "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3d2wlsFgp7Ge",
        "colab_type": "code",
        "outputId": "37174701-48d6-4659-b876-b5c54e761808",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# When target exists\n",
        "standard_binary_search(nums, 7)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gsYY1xYYq2b8",
        "colab_type": "code",
        "outputId": "7939b051-a09a-4acb-95fe-1176acf1992b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# When target does not exist\n",
        "standard_binary_search(nums, 42)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-1"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "soMDN2h2rBAi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "nums = [1, 3, 4, 4, 4, 4, 6, 7, 8]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S2xNrvB3rGnH",
        "colab_type": "code",
        "outputId": "f8e71161-bb9f-4a7c-a835-4d35b478d758",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# When there exists duplicates of the target\n",
        "standard_binary_search(nums, 4)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "E7xyot8ou6dh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title Binary Search with Lower Bound \n",
        "def lower_bound_bs(nums, t):\n",
        "  l, r = 0, len(nums) - 1\n",
        "  while l <= r:\n",
        "    mid = l + (r - l) // 2\n",
        "    if t <= nums[mid]: # move as left as possible\n",
        "      r = mid - 1\n",
        "    else:\n",
        "      l = mid + 1\n",
        "  return l\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FYrRsAqwwQvl",
        "colab_type": "code",
        "outputId": "83763de7-f709-4393-b9df-4a21a4a5354e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Binary Search with lower bound\n",
        "l1 = lower_bound_bs(nums, 4)\n",
        "l2 = lower_bound_bs(nums, 5)\n",
        "print(l1, l2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nGWDrHR12Rtq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title Binary Search with Upper Bound \n",
        "def upper_bound_bs(nums, t):\n",
        "  l, r = 0, len(nums) - 1\n",
        "  while l <= r:\n",
        "    mid = l + (r - l) // 2\n",
        "    if t >= nums[mid]: # move as right as possible\n",
        "      l = mid + 1\n",
        "    else:\n",
        "      r = mid - 1\n",
        "  return l\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VkCtss6P23RH",
        "colab_type": "code",
        "outputId": "d94adadf-a113-4de8-f1d0-73521ad65e13",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Binary Search with upper bound\n",
        "l1 = upper_bound_bs(nums, 4)\n",
        "l2 = upper_bound_bs(nums, 5)\n",
        "print(l1, l2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Mn8qGzZezFqe",
        "colab_type": "code",
        "outputId": "6dea4b52-ba92-43e1-a79a-85be699d343d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "#@title Use Python Module bisect\n",
        "from bisect import bisect_left,bisect_right, bisect\n",
        "l1 = bisect_left(nums, 4)\n",
        "r1 = bisect_right(nums, 5)\n",
        "l2 = bisect_right(nums, 4)\n",
        "r2 = bisect_right(nums, 5)\n",
        "p3 = bisect(nums, 5)\n",
        "print(l1, r1, l2, r2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2 6 6 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZYxs9WYC2DUk",
        "colab_type": "code",
        "outputId": "6cbfb9de-c542-437d-839c-1410ebdfebfd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "p1 = bisect_left(nums, 4)\n",
        "p2 = bisect_right(nums, 4)\n",
        "p3 = bisect(nums, 4)\n",
        "print(p1, p2, p3)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2 6 6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0Rfi8qZndFdd",
        "colab_type": "text"
      },
      "source": [
        "### Applications\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "A6ewzRSkRM5R",
        "colab_type": "text"
      },
      "source": [
        "#### Rotated Array"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "V_TzJ-H_kHTZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# First bad Version\n",
        "def firstBadVersion(self, n):\n",
        "    l, r = 1, n\n",
        "    while l <= r:\n",
        "        mid = l + (r - l) // 2\n",
        "        if isBadVersion(mid):\n",
        "            r = mid - 1\n",
        "        else:\n",
        "            l = mid + 1           \n",
        "    return l\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "310ELp0zcyWm",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def RotatedBinarySearch(nums, t):   \n",
        "      l, r = 0, len(nums)-1\n",
        "      while l <= r:\n",
        "          mid = l + (r-l)//2\n",
        "          if nums[mid] == t:\n",
        "              return mid\n",
        "          # Left is sorted\n",
        "          if nums[l] < nums[mid]: \n",
        "              if nums[l] <= t < nums[mid]:\n",
        "                  r = mid - 1\n",
        "              else:\n",
        "                  l = mid + 1\n",
        "          # Right is sorted\n",
        "          elif nums[l] > nums[mid]: \n",
        "              if nums[mid] < t <= nums[r]:\n",
        "                  l = mid + 1\n",
        "              else:\n",
        "                  r = mid - 1\n",
        "          # Left and middle index is the same, move to the right\n",
        "          else: \n",
        "              l = mid + 1\n",
        "      return -1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "abgMk_jNfSPV",
        "colab_type": "code",
        "outputId": "8dce0c66-850b-405a-dcf9-c031b5a98d2a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "nums = [7,0,1,2,3,4,5,6]\n",
        "RotatedBinarySearch(nums, 3)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DYQbczWuQ-UM",
        "colab_type": "text"
      },
      "source": [
        "####  Binary Search to Solve Math Problem"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6nq9BPxuRSI2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import math\n",
        "def arrangeCoins(n: int) -> int:\n",
        "    return int((math.sqrt(1+8*n)-1) // 2)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hF5v8wnARdAR",
        "colab_type": "code",
        "outputId": "6431df36-a202-4e41-aeec-1f5246592d7b",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "arrangeCoins(8)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8GAML-APRt4m",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Use Binary Search\n",
        "def arrangeCoins(n):\n",
        "    def isValid(row):\n",
        "        return (row * (row + 1)) // 2 <= n\n",
        "    \n",
        "    def bisect_right():\n",
        "        l, r = 1, n\n",
        "        while l <= r:\n",
        "            mid = l + (r-l) // 2\n",
        "            # Move as right as possible\n",
        "            if isValid(mid): \n",
        "                l = mid + 1\n",
        "            else:\n",
        "                r = mid - 1\n",
        "        return l\n",
        "    return bisect_right() - 1\n",
        "        "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cf1D07VYUYch",
        "colab_type": "code",
        "outputId": "98316869-95ad-4cef-8acb-790e05764cf1",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "arrangeCoins(8)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aVJePJSD3e16",
        "colab_type": "text"
      },
      "source": [
        "## Binary Search Tree"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bi9eVUn93YcR",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title Binary Tree Node\n",
        "class BiNode:\n",
        "  def __init__(self, val):\n",
        "    self.left = None\n",
        "    self.right = None\n",
        "    self.val = val"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "23mTR1N2wf4y",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# A helper function to print out the tree in order\n",
        "'''\n",
        "Yield from recursive function\n",
        "'''\n",
        "def inorder_print(root):\n",
        "  if not root:\n",
        "    return\n",
        "  yield from inorder_print(root.left)\n",
        "  yield root.val\n",
        "  yield from inorder_print(root.right)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "rh4tS_qnunWL",
        "colab_type": "text"
      },
      "source": [
        "### Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uPKnMRSAtX5d",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title  Recursive Search\n",
        "def search(root, t):\n",
        "  if not root:\n",
        "    return None\n",
        "  if root.val == t:\n",
        "    return root\n",
        "  elif t < root.val:\n",
        "    return search(root.left, t)\n",
        "  else:\n",
        "    return search(root.right, t)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yC6VSC6Gt6Rp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title  Iterative Search\n",
        "def searchItr(root, t):\n",
        "  while root:\n",
        "    if root.val == t:\n",
        "      return root\n",
        "    elif t < root.val:\n",
        "      root = root.left\n",
        "    else:\n",
        "      root = root.right\n",
        "  return None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Ps9yX8EgXGp2",
        "colab_type": "text"
      },
      "source": [
        "### Minimum and Maximum Node"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "93wNIzgDXFdN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# minimum recursive\n",
        "def minimum(root):\n",
        "  if not root:\n",
        "    return None\n",
        "  if not root.left:\n",
        "    return root\n",
        "  return minimum(root.left)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YKk-aYiZXej7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# minimum iterative\n",
        "def minimumIter(root):\n",
        "  while root:\n",
        "    if not root.left:\n",
        "      return root\n",
        "    root = root.left\n",
        "  return None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "eb-sC2VbYa4k",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# maximum recursive\n",
        "def maximum(root):\n",
        "  if not root:\n",
        "    return None\n",
        "  if not root.right:\n",
        "    return root\n",
        "  return maximum(root.right)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5NLBVCo-YfcI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# maximum iterative\n",
        "def maximumIter(root):\n",
        "  while root:\n",
        "    if not root.right:\n",
        "      return root\n",
        "    root = root.right\n",
        "  return None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vRjlkcWbfuJ4",
        "colab_type": "text"
      },
      "source": [
        "### Predecessor and Successor"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JUS3EHJ_Rb8C",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Successor found with inorder\n",
        "def successorInorder(root, node):\n",
        "  if not node:\n",
        "    return None\n",
        "  if node.right is not None:\n",
        "    return minimum(node.right)\n",
        "  # Inorder traversal\n",
        "  succ = None\n",
        "  while root:      \n",
        "    if node.val > root.val:\n",
        "      root = root.right\n",
        "    elif node.val < root.val:\n",
        "      succ = root\n",
        "      root = root.left\n",
        "    else:\n",
        "      break\n",
        "  return succ"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LJSGRwcpfy_x",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def reverse(node):\n",
        "  if not node or not node.p:\n",
        "    return None\n",
        "  # node is a left child\n",
        "  if node.val < node.p.val:\n",
        "    return node.p\n",
        "  return reverse(node.p)\n",
        "\n",
        "# Successor when the target node is not directly given\n",
        "def successor(root, t):\n",
        "  # Traverse backward and see if a node is a left child\n",
        "  def reverse(node):\n",
        "    if not node or not node.p:\n",
        "      return None\n",
        "    # node is a left child\n",
        "    if node.val < node.p.val:\n",
        "      return node.p\n",
        "    return reverse(node.p)\n",
        "  \n",
        "  # Find the target and set its parent while searching\n",
        "  def helper(root, t):\n",
        "    # t is not found\n",
        "    if not root:\n",
        "      return None\n",
        "    if t == root.val: \n",
        "      if root.right:\n",
        "        return minimum(root.right)\n",
        "      else:\n",
        "        return reverse(root)\n",
        "    elif t < root.val:\n",
        "      root.left.p = root\n",
        "      return helper(root.left, t)\n",
        "    else:\n",
        "      root.right.p = root\n",
        "      return helper(root.right, t)\n",
        "    \n",
        "  root.p = None\n",
        "  return helper(root, t)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9EYUc_lwoKSi",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Separate the above code into two steps\n",
        "def findNodeAddParent(root, t):\n",
        "  if not root:\n",
        "    return None\n",
        "  if t == root.val: \n",
        "    return root\n",
        "  elif t < root.val:\n",
        "    root.left.p = root\n",
        "    return findNodeAddParent(root.left, t)\n",
        "  else:\n",
        "    root.right.p = root\n",
        "    return findNodeAddParent(root.right, t)\n",
        "\n",
        "# Find successor from a given node\n",
        "def successor2(root):\n",
        "  if not root:\n",
        "    return None\n",
        "  if root.right:\n",
        "    return minimum(root.right)\n",
        "  else:\n",
        "    return reverse(root) "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9mwSazjPUEEN",
        "colab_type": "text"
      },
      "source": [
        "Predecessor"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AOinBcdcUGRG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def reverse_right(node):\n",
        "  if not node or not node.p:\n",
        "    return None\n",
        "  # node is a right child\n",
        "  if node.val > node.p.val:\n",
        "    return node.p\n",
        "  return reverse_right(node.p)\n",
        "\n",
        "def predecessor(root):\n",
        "  if not root:\n",
        "    return None\n",
        "  if root.left:\n",
        "    return maximum(root.left)\n",
        "  else:\n",
        "    return reverse_right(root) "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nRiIVBZsUucH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# predecessor inorder\n",
        "def predecessorInorder(root, node):\n",
        "  if not node:\n",
        "    return None\n",
        "  if node.left is not None:\n",
        "    return maximum(node.left)\n",
        "  # Inorder traversal\n",
        "  pred = None\n",
        "  while root:      \n",
        "    if node.val > root.val:\n",
        "        pred = root\n",
        "        root = root.right\n",
        "    elif node.val < root.val:\n",
        "      root = root.left\n",
        "    else:\n",
        "      break\n",
        "  return pred"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t2ATJStuvPvu",
        "colab_type": "text"
      },
      "source": [
        "### Insert"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9HdUHb-yvbO3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Clean Recursive Insert\n",
        "def insert(root, t):\n",
        "  if not root:\n",
        "    return BiNode(t)\n",
        "  if root.val == t:\n",
        "    return root\n",
        "  elif t < root.val:\n",
        "    root.left = insert(root.left, t)\n",
        "    return root\n",
        "  else:\n",
        "    root.right = insert(root.right, t) \n",
        "    return root"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Cqb911P_1ocX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Recursive Insert 2\n",
        "def insert2(root, t):\n",
        "  if not root:\n",
        "    return \n",
        "  if root.val == t:\n",
        "    return \n",
        "  elif t < root.val:\n",
        "    if not root.left:\n",
        "      root.left = BiNode(t)\n",
        "    else:\n",
        "      insert2(root.left, t)\n",
        "  else:\n",
        "    if not root.right:\n",
        "      root.right = BiNode(t)\n",
        "    else:\n",
        "      insert2(root.right, t) "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QN6MwXa16jUI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Iterative insertion\n",
        "def insertItr(root, t):\n",
        "  p = None\n",
        "  node = root #Keep the root node\n",
        "  while node:\n",
        "    # Node exists already\n",
        "    if node.val == t:\n",
        "      return root\n",
        "    if t > node.val:\n",
        "      p = node\n",
        "      node = node.right\n",
        "    else:\n",
        "      p = node\n",
        "      node = node.left\n",
        "  # Assign new node\n",
        "  if not p:\n",
        "    root = BiNode(t)\n",
        "  elif t > p.val:\n",
        "    p.right = BiNode(t)\n",
        "  else:\n",
        "    p.left = BiNode(t)\n",
        "  return root\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BJUGXsoBYI5O",
        "colab_type": "text"
      },
      "source": [
        "### Delete"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nRVCru44YORz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def deleteMinimum(root):\n",
        "  if not root:\n",
        "    return None, None\n",
        "  if root.left:\n",
        "    mini, left = deleteMinimum(root.left)\n",
        "    root.left = left\n",
        "    return mini, root\n",
        "  # the minimum node\n",
        "  if not root.left: \n",
        "    return root, None \n",
        "\n",
        "def _delete(root):\n",
        "  if not root:\n",
        "    return None\n",
        "  # No chidren: Delete it\n",
        "  if not root.left and not root.right:\n",
        "    return None \n",
        "  # Two children: Copy the value of successor\n",
        "  elif all([root.left, root.right]):\n",
        "    succ, right = deleteMinimum(root.right)\n",
        "    root.val = succ.val\n",
        "    root.right = right\n",
        "    return root\n",
        "  # One Child: Copy the value\n",
        "  else:\n",
        "    if root.left:\n",
        "      root.val = root.left.val\n",
        "      root.left = None\n",
        "    else:\n",
        "      root.val = root.right.val\n",
        "      root.right = None\n",
        "    return root\n",
        "  \n",
        "def delete(root, t):\n",
        "  if not root:\n",
        "    return\n",
        "  if root.val == t:\n",
        "    root = _delete(root)\n",
        "    return root \n",
        "  elif t > root.val:\n",
        "    root.right = delete(root.right, t)\n",
        "    return root\n",
        "  else:\n",
        "    root.left = delete(root.left, t)\n",
        "    return root\n",
        "  \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8pAODLP1ktWy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "keys = [8, 3, 10, 1, 6, 14, 4, 7, 13]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xW555Xb6wCb4",
        "colab_type": "code",
        "outputId": "127d98c4-453d-4873-f714-8ddaec9356ff",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# Construct the examplary tree\n",
        "%%time\n",
        "root = None\n",
        "for k in keys:\n",
        "  root = insert(root, k)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CPU times: user 21 µs, sys: 4 µs, total: 25 µs\n",
            "Wall time: 28.8 µs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TL9-6VMI2Ldn",
        "colab_type": "code",
        "outputId": "e206db54-d2e4-46fe-a5ef-33c8c40f9346",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# Construct the examplary tree\n",
        "%%time\n",
        "root = BiNode(keys[0])\n",
        "for k in keys[1:]:\n",
        "  insert2(root, k)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CPU times: user 54 µs, sys: 0 ns, total: 54 µs\n",
            "Wall time: 60.6 µs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NoBJCgvF7WVo",
        "colab_type": "code",
        "outputId": "2905fd04-9de0-4e1b-d809-562698194c57",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# Construct the examplary tree\n",
        "%%time\n",
        "root = BiNode(keys[0])\n",
        "for k in keys:\n",
        "  root = insertItr(root, k)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "CPU times: user 49 µs, sys: 0 ns, total: 49 µs\n",
            "Wall time: 103 µs\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vsV8Y2vkwbDI",
        "colab_type": "code",
        "outputId": "d7491e7c-606c-4d0e-9cf0-d4424d7cf3fd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# insert key 9 \n",
        "out_keys = inorder_print(root)\n",
        "for k in out_keys:\n",
        "  print(k, end = ' ')"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 3 4 6 7 8 10 13 14 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nRzeShLMXuIP",
        "colab_type": "code",
        "outputId": "ab5374c1-af90-4292-9e84-2688ce6d6674",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "## Test Minimum and maximum\n",
        "print(minimum(root).val, minimumIter(root).val,maximum(root).val, maximumIter(root).val)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 1 14 14\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oJONUENtl654",
        "colab_type": "code",
        "outputId": "fc34abec-bc1d-408e-be64-c1a9c51edf35",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        }
      },
      "source": [
        "# Test successor and predecessor\n",
        "s1 = successor(root, 14)\n",
        "s2 = successor(root, 3)\n",
        "s3 = successor(root, 4)\n",
        "s4 = successor(root, 7)\n",
        "if s1:\n",
        "  print(s1)\n",
        "print(s2.val, s3.val, s4.val)\n",
        "root.p = None\n",
        "node = findNodeAddParent(root, 4)\n",
        "suc = successor2(node)\n",
        "print(suc.val)\n",
        "print(predecessorInorder(root, suc).val, successorInorder(root, suc).val)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "4 6 8\n",
            "6\n",
            "4 7\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ee9SU288b91o",
        "colab_type": "code",
        "outputId": "7bc7bdd8-e5ec-4c75-a631-a4950bb80b00",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "# Test Delete\n",
        "out_keys = inorder_print(root)\n",
        "for k in out_keys:\n",
        "  print(k, end = ' ')\n",
        "print(' ,')\n",
        "root1 = delete(root, 3)\n",
        "out_keys = inorder_print(root1)\n",
        "for k in out_keys:\n",
        "  print(k, end = ' ')\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 3 4 6 7 8 10 13 14  ,\n",
            "1 4 6 7 8 10 13 14 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "muAC9qyz3sXJ",
        "colab_type": "text"
      },
      "source": [
        "## Segment Tree"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "weAxbsyJ3rrO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class TreeNode:\n",
        "  def __init__(self, val, s, e):\n",
        "    self.val = val\n",
        "    self.s = s\n",
        "    self.e = e\n",
        "    self.left = None\n",
        "    self.right = None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DWTvjBm06N7N",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def getNodes(root):\n",
        "  if not root:\n",
        "    return []\n",
        "  left = getNodes(root.left)\n",
        "  right = getNodes(root.right)\n",
        "  return left + [(root.s, root.e, root.val)] + right"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3tPVDCeE4MFX",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def merge(left, right, s, e):\n",
        "  return TreeNode(left.val + right.val, s, e)\n",
        "\n",
        "def _buildSegmentTree(nums, s, e):\n",
        "  '''\n",
        "   s, e: start index and end index\n",
        "  '''\n",
        "  if s > e:\n",
        "      return None\n",
        "  if s == e:\n",
        "      return TreeNode(nums[s], s, e)\n",
        "  \n",
        "  m = (s + e)//2\n",
        "  # Divide: return a subtree \n",
        "  left = _buildSegmentTree(nums, s, m)\n",
        "  right = _buildSegmentTree(nums, m+1, e)\n",
        "  \n",
        "  # Conquer: merge two subtree\n",
        "  node = TreeNode(left.val + right.val, s, e)\n",
        "  node.left = left\n",
        "  node.right = right\n",
        "  return node"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_11QSpH8901s",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Range Query\n",
        "def _rangeQuery(root, i, j, s, e): \n",
        "  if s == i and j == e:\n",
        "    return root.val if root else 0 \n",
        "  m = (s + e)//2\n",
        "  if j <= m:\n",
        "    return _rangeQuery(root.left, i, j, s, m)\n",
        "  elif i > m:\n",
        "    return _rangeQuery(root.right, i, j, m+1, e)\n",
        "  else:\n",
        "    return _rangeQuery(root.left, i, m, s, m) + _rangeQuery(root.right, m+1, j, m+1, e)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aAc6LT911CDs",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Update\n",
        "def _update(root, s, e, i, val):\n",
        "  if s == e == i:\n",
        "    root.val = val\n",
        "    return \n",
        "  m = (s + e) // 2\n",
        "  if i <= m:\n",
        "    _update(root.left, s, m, i, val)\n",
        "  else:\n",
        "    _update(root.right, m + 1, e, i, val)\n",
        "  root.val = root.left.val + root.right.val\n",
        "  return "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YaBuyWTr5WHH",
        "colab_type": "code",
        "outputId": "450f71db-3588-47cf-d556-46f2436a735c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Test tree construction\n",
        "nums = [2, 9, 4, 5, 8, 7]\n",
        "root = _buildSegmentTree(nums, 0, len(nums) - 1)\n",
        "print(getNodes(root))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[(0, 0, 2), (0, 1, 11), (1, 1, 9), (0, 2, 15), (2, 2, 4), (0, 5, 35), (3, 3, 5), (3, 4, 13), (4, 4, 8), (3, 5, 20), (5, 5, 7)]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mEzfRgUS-UH4",
        "colab_type": "code",
        "outputId": "a0f13949-6215-49fc-ceae-b6cfdc500788",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Test Range Query\n",
        "print(_rangeQuery(root, 0, 2, 0, len(nums) - 1))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "15\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sqy_bZWr2AAw",
        "colab_type": "code",
        "outputId": "10c13b8d-9c44-41d3-e0aa-3f0caff4bb3e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "# Test updates\n",
        "_update(root,  0, len(nums) - 1, 1, 3)\n",
        "print(_rangeQuery(root, 0, 2, 0, len(nums) - 1))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "9\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}